package org.apache.commons.graph.utils

import org.apache.commons.graph.GraphException
import org.apache.commons.graph.model.BaseLabeledEdge
import org.apache.commons.graph.model.BaseLabeledVertex
import org.apache.commons.graph.model.BaseMutableGraph
import org.apache.commons.graph.model.UndirectedMutableGraph

/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements.  See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership.  The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License.  You may obtain a copy of the License at
*
*   http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied.  See the License for the
* specific language governing permissions and limitations
* under the License.
*/

/**
 * Utilities graph class.
 */
object GraphUtils {
    /**
     * Create a Biparted graph
     *
     * @param nVertices number of vertices
     * @param g graph
     */
    fun buildBipartedGraph(nVertices: Int, g: UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>) {
        // building Graph
        for (i in 0..<nVertices) {
            val v = BaseLabeledVertex(i.toString())
            g.addVertex(v)
        }

        val fistPartition: MutableList<BaseLabeledVertex> = ArrayList()
        val secondPartition: MutableList<BaseLabeledVertex> = ArrayList()

        var count = 0
        for (v1 in g.vertices) {
            if (count++ == nVertices / 2) {
                break
            }
            fistPartition.add(v1)
        }

        count = 0
        for (v2 in g.vertices) {
            if (count++ < nVertices / 2) {
                continue
            }
            secondPartition.add(v2)
        }

        for (v1 in fistPartition) {
            for (v2 in secondPartition) {
                if (!v1.equals(v2)) {
                    try {
                        g.addEdge(v1, BaseLabeledEdge(String.format("%s -> %s", v1, v2)), v2)
                    } catch (e: GraphException) {
                        // ignore
                    }
                }
            }
        }
    }

    /**
     * Creates a complete graph with nVertices
     *
     * @param nVertices number of vertices
     * @param g graph
     */
    fun buildCompleteGraph(nVertices: Int, g: BaseMutableGraph<BaseLabeledVertex, BaseLabeledEdge>) {
        // building Graph
        for (i in 0..<nVertices) {
            val v = BaseLabeledVertex(i.toString())
            g.addVertex(v)
        }

        for (v1 in g.vertices) {
            for (v2 in g.vertices) {
                if (!v1.equals(v2)) {
                    try {
                        g.addEdge(v1, BaseLabeledEdge(String.format("%s -> %s", v1, v2)), v2)
                    } catch (e: GraphException) {
                        // ignore
                    }
                }
            }
        }
    }

    fun buildCrownGraph(nVertices: Int, g: UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>) {
        val tmp: MutableList<BaseLabeledVertex> = ArrayList()

        for (i in 0..<nVertices) {
            val v = BaseLabeledVertex(i.toString())
            g.addVertex(v)
            tmp.add(v)
        }

        for (i in 0..<nVertices) {
            var next = i + 1
            if (i == (nVertices - 1)) {
                next = 0
            }
            val e = BaseLabeledEdge(String.format("%s -> %s", i, next))
            try {
                g.addEdge(tmp[i], e, tmp[next])
            } catch (ge: GraphException) {
                // ignore
            }
        }
    }

    /**
     * Creates a graph that contains all classic sudoku contratints.
     *
     * @return
     */
    fun buildSudokuGraph(sudoku: UndirectedMutableGraph<BaseLabeledVertex, BaseLabeledEdge>): Array<Array<BaseLabeledVertex>> {
        val grid = Array<Array<BaseLabeledVertex?>>(9) { arrayOfNulls(9) }
        // build sudoku grid.
        for (row in 0..8) {
            for (col in 0..8) {
                grid[row][col] = BaseLabeledVertex(String.format("%s, %s", row, col))
                sudoku.addVertex(grid[row][col]!!)
            }
        }

        val rowsOffsets = intArrayOf(0, 3, 6)
        val colsOffsets = intArrayOf(0, 3, 6)

        // build constraint.
        for (rof in 0..2) {
            for (cof in 0..2) {
                val boxes: MutableList<BaseLabeledVertex> = ArrayList()
                for (row in rowsOffsets[rof]..<3 + rowsOffsets[rof]) {
                    for (col in colsOffsets[cof]..<3 + colsOffsets[cof]) {
                        boxes.add(grid[row][col]!!)
                    }
                }

                for (v1 in boxes) {
                    for (v2 in boxes) {
                        val e = BaseLabeledEdge(String.format("%s -> %s", v1, v2))
                        if (!v1.equals(v2)) {
                            try {
                                sudoku.addEdge(v1, e, v2)
                            } catch (ge: GraphException) {
                                // ignore
                            }
                        }
                    }
                }
            }
        }

        // create rows constraint
        for (j in 0..8) {
            for (i in 0..8) {
                for (h in 0..8) {
                    val v1 = grid[j][i]!!
                    val v2 = grid[j][h]!!

                    if (v1 != v2) {
                        val e = BaseLabeledEdge(String.format("%s -> %s", v1, v2))
                        try {
                            sudoku.addEdge(v1, e, v2)
                        } catch (ge: GraphException) {
                            // ignore
                        }
                    }
                }
            }
        }

        // create cols constraint
        for (j in 0..8) {
            for (i in 0..8) {
                for (h in 0..8) {
                    val v1 = grid[i][j]!!
                    val v2 = grid[h][j]!!

                    if (!v1.equals(v2)) {
                        val e = BaseLabeledEdge(String.format("%s -> %s", v1, v2))
                        try {
                            sudoku.addEdge(v1, e, v2)
                        } catch (ge: GraphException) {
                            // ignore
                        }
                    }
                }
            }
        }
        return grid as Array<Array<BaseLabeledVertex>>
    }
}
